package com.example.zzy.zzytest.algo.sort.bucket;

import java.util.Arrays;

/**
 * 基数排序:将整数按位数切割成不同的数字，然后按每个位数分别比较。
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] testArr = new int[]{290, 395, 13, 549, 79, 137, 214, 43};
        int maxValue = getMaxValue(testArr);
        int maxDigit = (maxValue + "").length();
        testArr = radixSort(testArr, maxDigit);
        for (int i : testArr) {
            System.out.print(i + " ");
        }
    }

    public static int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;
        for (int i = 0; i < maxDigit; i++, dev *= 10) {
            //考虑复数的情况，扩充一倍的桶,[0-9]负,[10-19]正数
            int[][] buckets = new int[20][0];

            //从个位开始，放进桶
            for (int j = 0; j < arr.length; j++) {
                int curDigit = (arr[j] / dev) % mod;
                buckets[curDigit] = arrAppend(buckets[curDigit], arr[j]);
            }

            //放完后统一在输出到原arr
            int index = 0;
            for (int[] curBucket : buckets) {
                for (int val : curBucket) {
                    arr[index++] = val;
                }
            }
        }

        return arr;
    }

    //扩充一位并复制数据
    private static int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    public static int getMaxValue(int[] arr) {
        int max = arr[0];
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
        }
        return max;
    }
}
